package demo1;

public class DynamicPlanningPractise {
    /**
     * 二维费用dp问题
     * 一和零
     * 时间复杂度O（n*n*n）
     * 空间复杂度O（n*n*n）*/
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        //1 创建dp表 - 使用虚拟位置法进行创建
        int[][][] dp = new int[len+1][m+1][n+1];
        //2 初始化 - 无需初始化
        //3 填表
        for(int i = 1; i <= len; i++) {
            //第一层循环表示前i个元素，由于我们是根据最后一个元素进行划分问题，故需要计算最后一个元素1和0的个数
            int a = 0, b = 0;
            for(char ch : strs[i-1].toCharArray())
                if(ch=='0') a++;
                else b++;
            for(int j = 0; j <= m; j++) {
                for(int k = 0; k <= n; k++) {
                    dp[i][j][k] = dp[i-1][j][k];
                    if(a<=j && b<=k)
                        dp[i][j][k] = Math.max(dp[i-1][j-a][k-b]+1,dp[i][j][k]);
                }
            }
        }
        //4 返回值
        return dp[len][m][n];
    }

    /**
     * 一和零 - 滚动数组优化
     * 时间复杂度O（n*n*n）- 实际比这个小
     * 空间复杂度O（n*n）*/
    public int findMaxFormOther(String[] strs, int m, int n) {
        int len = strs.length;
        //1 创建dp表 - 使用虚拟位置法进行创建
        int[][] dp = new int[m+1][n+1];
        //2 初始化 - 无需初始化
        //3 填表
        for(int i = 0; i < len; i++) {
            //第一层循环表示前i个元素，由于我们是根据最后一个元素进行划分问题，故需要计算最后一个元素1和0的个数
            int a = 0, b = 0;
            for(char ch : strs[i].toCharArray())
                if(ch=='0') a++;
                else b++;
            //当我们使用滚动数组时，需要将填表顺序进行修改（若无强制要求）
            for(int j = m; j >= a; j--)
                for(int k = n; k>= b; k--)
                    dp[j][k] = Math.max(dp[j-a][k-b]+1,dp[j][k]);
        }
        //4 返回值
        return dp[m][n];
    }
}
